package com.googlecode.lohr.parser.combinators.matcher;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Stack;

import com.googlecode.lohr.parser.combinators.MatchResults;

/**
 * A MatchContext is used to invoke parse text by invoking the doMatch method 
 * and passing a Matcher.
 * 
 * MatchContext manages the parsing process.
 * MatchContext implements strategies for memoizing match results 
 * and avoiding recursion.
 * 
 * Specificially, MatchContext avoids left recursion using the techniques 
 * described in the paper "Packrat Parsers Can Support Left Recursion" by
 * Alessandro Warth, James R Douglas, and Todd Millstein 
 *   
 * @author ted stockwell
 *
 */
public class MatchContext {
	private static final long serialVersionUID = 1L;
	
	public static class MatchRequest {
		public Matcher matcher;
		public int start;
		public MatchResults results;
		public boolean cached= false;
		public List<MatchRequest> children= new ArrayList<MatchRequest>(1);
		public MatchRequest(Matcher matcher, int start) {
			this.matcher= matcher;
			this.start= start;
		}
	}

	static class CacheEntry {
		MatchResults results;
		int position;
		CacheEntry(MatchResults results, int position) {
			this.results= results;
			this.position= position;
		}
	}
	static class MatchCall extends MatchResults {
		boolean recursionDetected= false;
		private Map<MatchCall, RecursionHead> heads= null;
		Matcher matcher;
		MatchResults seed;
		MatchCall(Matcher matcher, int start) {
			super("placeholder", start);
			this.matcher= matcher;
		}
		
		boolean isInvolvedInRecursion() {
			return heads != null && !heads.isEmpty();
		}
		
		RecursionHead getHead(MatchCall call) {
			if (heads == null)
				return null;
			return heads.get(call);
		}
		void putHead(MatchCall call, RecursionHead head) {
			if (heads == null)
				heads= new HashMap<MatchContext.MatchCall, MatchContext.RecursionHead>();
			heads.put(call, head);
		}
	}
	static class RecursionHead {
		HashMap<Matcher, Integer> involvedMatchers= new HashMap<Matcher, Integer>();
		HashMap<Matcher, Integer> evalMatchers= new HashMap<Matcher, Integer>();
		Matcher causingMatcher;
		RecursionHead(Matcher matcher) {
			causingMatcher= matcher;
		}
	}
	
	
	
	private String _input;
	private HashMap<Matcher, Map<Integer, CacheEntry>> _cache= 
		new HashMap<Matcher, Map<Integer,CacheEntry>>();
	private Map<Integer, Stack<MatchCall>> _stacks= new HashMap<Integer, Stack<MatchCall>>();
	private Map<Integer, Stack<RecursionHead>> _heads= new HashMap<Integer, Stack<RecursionHead>>();
	
	private boolean _trace= true;
	private int _tabs= 0;
	private HashMap<Matcher, Boolean> _traceFlags= new HashMap<Matcher, Boolean>();
	
	public static MatchResults match(Matcher matcher, String input) {
		return new MatchContext(input).doMatch(matcher, 0);
	}
	
	static class MatchRecord {
		
	}
	
	
	public MatchContext(String input) {
		_input= input;
	}
	
	public MatchResults doMatch(Matcher matcher, int start, boolean trace) {
		trace(matcher, trace);
		return doMatch(matcher, start);
	}
	
	/**
	 * This method is used to perform matches.
	 */
	public MatchResults doMatch(Matcher matcher, int start) {

		// setup trace 
		boolean otrace= _trace;
		Boolean traceFlag= _traceFlags.get(matcher);
		if (traceFlag != null) 
			_trace= traceFlag.booleanValue();
		boolean trace= _trace;
		if (matcher.getLabel().contains("."))
			trace= false;
		if (trace) _tabs++;
		String tabs= ""; for (int i= _tabs; 0 < i--;) tabs+= "\t"; 		
		if (trace) System.out.println(tabs+"doMatch("+matcher.getLabel()+","+start+")");		
		try {
		
		Stack<MatchCall> stack= _stacks.get(start);
		if (stack == null) 
			_stacks.put(start, stack= new Stack<MatchCall>());
		
		// return any cached results
		CacheEntry entry= getCachedResults(matcher, start);
		if (entry != null) {
			if (entry.results instanceof MatchCall) { 
				MatchCall call= (MatchCall)entry.results;
				setupRecursionProcessing(call);
if (trace)System.out.println(tabs+"return recursion detected:"+matcher.getLabel());		
				return new MatchResults("fail, recursion detected:"+matcher.getLabel(), start);
			}
if (trace)System.out.println(tabs+"return cached results:"+entry.results);		
			return entry.results;
		}
		
		// put match call in cache
		MatchCall call= new MatchCall(matcher, start);
		entry= cacheMatchResults(call, matcher, start);

		// add to call stack for this position
		stack.push(call);
		
		// evaluate matcher 
		MatchResults results= matcher.match(this, start);
		
		stack.pop(); // pop call off call stack
		
		if (call.heads != null && !call.heads.isEmpty()) {  
			// recursion detected
			RecursionHead head= call.getHead(call);
			if (head != null) { // this call is a recursion head
				if (results.success())  
if (trace)System.out.println(tabs+"grow results:"+results);		
					results= growResults(matcher, start, results, head);
				entry.results= results;
			}
		}
		else
			entry.results= results;
		
		
if (trace)System.out.println(tabs+"return results:"+results);		
		return results;
		
		} finally {
			if (trace) {
				System.out.println(tabs+"/doMatch");		
				_tabs--;
			}
			_trace= otrace;
		}
	}
	
	private MatchResults growResults(Matcher matcher, int start, MatchResults results, RecursionHead head) {
		
		// denote the current recursion being processed
		Stack<RecursionHead> heads= _heads.get(start);
		if (heads == null)
			_heads.put(start, heads= new Stack<MatchContext.RecursionHead>()); 
		heads.push(head); 
		
		head.evalMatchers= new HashMap<Matcher,Integer>(head.involvedMatchers);

		while (true) {
			MatchResults grownResults= matcher.match(this, start);
			if (!grownResults.success() && !(grownResults instanceof MatchCall))
				break;
			if (grownResults.longestLength() <= results.longestLength())
				break;
			results= grownResults;
		}
		
		heads.pop(); // done processing recursion
		
		return results;
	}

	private void setupRecursionProcessing(MatchCall headCall) {
		RecursionHead head= headCall.getHead(headCall);
		if (head == null)
			headCall.putHead(headCall, head= new RecursionHead(headCall.matcher));
		Stack<MatchCall> callStack= _stacks.get(headCall.position);
		for (int i= callStack.size(); 0 < i--;) {
			MatchCall call= callStack.get(i);
			RecursionHead h= call.getHead(headCall);
			if (h == head)
				break;
			call.putHead(headCall, head);
			
			Integer count= head.involvedMatchers.get(call.matcher);
			if (count == null) {
				head.involvedMatchers.put(call.matcher, 1);
			}
			else 
				count= count+1;
			head.involvedMatchers.put(call.matcher, count);
		}
	}

	public String getInput() {
		return _input;
	}

	protected void clearCachedResults(Matcher matcher, int start) {
		Map<Integer,CacheEntry> entries= _cache.get(matcher);
		entries.remove(start);
	}
	
	public CacheEntry getCachedResults(Matcher matcher, int start) {
		CacheEntry entry= null;
		Map<Integer,CacheEntry> entries= _cache.get(matcher);
		if (entries != null)
			entry= entries.get(start);
		
		// if not growing a seed parse then just return the cached entry
		Stack<RecursionHead> heads= _heads.get(start);
		if (heads == null || heads.isEmpty()) {
			
			// do not return cached seed results if this call will not be revisited during the growth phase
			if (entry!= null && entry.results instanceof MatchCall) {
				MatchCall call= (MatchCall)entry.results;
				if (call.isInvolvedInRecursion()) {
					Stack<MatchCall> stack= _stacks.get(start);
					if (!stack.lastElement().isInvolvedInRecursion())
						return null;
				}
			}
			
			return entry;
		}

		RecursionHead head= heads.lastElement();
		
//// original authors put in this guard in order to make sure that PEG behavior (only one result) was preserved.
//// this implementation is for parser combinators it is excluded		
//		// Growing a seed parse...
//		// Do not evaluate any rule that is not involved in the current left 
//		// recursion.
//		if (entry == null && matcher != head.causingMatcher && !head.involvedMatchers.contains(matcher))
//			return new CacheEntry(new MatchResults("rule not involved in the current recursion", start), start);
		
		// allow involved rules to be evaluated, but only once, during a 
		// seed-growing iteration.
		Integer count= head.evalMatchers.get(matcher);
		if (count != null && 0 < count) {
			head.evalMatchers.put(matcher, count-1);
			MatchResults results= matcher.match(this, start);
			entry= cacheMatchResults(results, matcher, start);
		}
		
		return entry;
	}
	
	protected CacheEntry cacheMatchResults(MatchResults matchResults, Matcher matcher, int start) {
		Map<Integer,CacheEntry> results= _cache.get(matcher);
		if (results == null) {
			results= new HashMap<Integer, CacheEntry>();
			_cache.put(matcher, results);
		}
		CacheEntry entry= results.get(start);
		if (entry == null) {
			entry= new CacheEntry(matchResults, start);
		}
		else
			entry.results= matchResults;
		results.put(start, entry);
		return entry;
	}
	
	public void trace(Matcher matcher, boolean trace) {
		_traceFlags.put(matcher, trace ? Boolean.TRUE : Boolean.FALSE);
	}
}
